def lengthOfLIS(nums: [int]) -> int:
    tails, res = [0] * len(nums), 0
    for num in nums:
        i, j = 0, res
        while i < j:
            m = (i + j) // 2
            if tails[m] < num: i = m + 1 # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
            else: j = m
        tails[i] = num
        print(tails)
        if j == res: res += 1
    return res

if __name__ == "__main__":
    a = [1, 2, 3, 4, 111, 222, 333, 5, 6, 7, 8, 9]
    print(lengthOfLIS(a))
